package com.ma.LinkedList;

import java.util.HashMap;

public class Linked {

    //如果链表有偶数个返回上中点，奇数个返回中电
    public static Node midOrUpMidNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    //如果链表有偶数个返回上中点，奇数个返回中电
    //如果链表有偶数个返回下中点，奇数个返回中电
    //如果链表有偶数个返回上中点前一个，奇数个返回中电
    //如果链表有偶数个返回下中点前一个，奇数个返回中电


    /**
     * 判断某链表是否是回文结构 (面试)
     * 笔试：将后半段扔进堆中，再跳出来一个一个比较
     *
     * @param head
     * @return
     */
    public static boolean Palindrome1(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node reverse = head;
        Node own = head;
        while (head.next != null && head.next.next != null) {
            reverse = reverse.next;//mid
            own = own.next.next;//end
        }

        own = reverse.next;
        reverse.next = null;
        Node record = null;
        //将后半段逆序
        while (own != null) {
            record = own.next;
            own.next = reverse;
            reverse = own;
            own = record;
        }
        record = reverse;
        own = head;
        boolean res = true;
        while (reverse != null && own != null) {
            if (reverse.value != own.value) {
                res = false;
                break;
            }
            reverse = record.next;
            own = own.next;
        }


        reverse = record.next;
        record.next = null;
        //将后半段逆序回来
        while (reverse != null) {
            own = reverse.next;
            reverse.next = record;
            record = reverse;
            reverse = own;
        }


        return res;
    }


    /**
     * 将链表划分为小于等于大于区域 (面试)
     * 笔试：遍历扔进数值然后快排，再创造新的链表返回
     *
     * @param head
     * @param pivot
     * @return
     */
    public static Node linkedPartion(Node head, int pivot) {
//        小于头与尾
        Node sH = null;
        Node sT = null;
//        等于头与尾
        Node eH = null;
        Node eT = null;
//        大于头与尾
        Node mH = null;
        Node mT = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sH == null) {
                    sH = head;
                    sT = head;
                } else {
                    sT.next = head;
                    sT = head;
                }

            } else if (head.value == pivot) {
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                if (eH == null) {
                    mH = head;
                    mT = head;
                } else {
                    mT.next = head;
                    mT = head;
                }
            }

            head = next;

        }


        //小于区域存在时
        if (sT != null) {
            sT.next = eH;
            eT = eT == null ? sT : eT;
        }

        //等于区域存在时
        if (eH != null) {
            eT.next = mH;
        }

        //如果小于区域不存在就判断等于区域是否存在，如果都不存在大于区域一定存在
        //sh~sT->eH~eT->mH~mT
        return sH != null ? sH : (eH != null ? eH : mH);

    }


    /**
     * 利用哈希表复制带环状结构的双链表
     *
     * @param head
     * @return
     */
    public static NodePlus copyListWithRand(NodePlus head) {
        HashMap<NodePlus, NodePlus> map = new HashMap<>();
        NodePlus cur = head;
        while (cur != null) {

            //      旧   新
            map.put(cur, new NodePlus(cur.value));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }


        return map.get(head);

    }


    /**
     * 非哈希表方式复制环状双链表
     *
     * @param head
     * @return
     */
    public static NodePlus copyList(NodePlus head) {
        if (head == null) {
            return null;
        }
        NodePlus cur = head;
        NodePlus next = null;


        //在head之间插入新的copy节点
        //1->2  ->   1->1`->2
        while (cur != null) {
            next = cur.next;
            cur.next = new NodePlus(cur.value);
            cur.next.next = next;

            cur = next;
        }
        cur = head;
        NodePlus copy = null;
        //拷贝rand的到copy节点上
        while (cur != null) {
            next = cur.next.next;
            copy = copy.next;
            copy.rand = cur.rand != null ? copy.rand.next : null;
            cur = next;
        }
        NodePlus res = head.next;
        copy = head;
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            cur.next = next;
            copy.next = next != null ? next.next : null;
            cur = next;


        }

        return res;


    }


    /**
     * 如果有环返回交点，无环返回null
     *
     * @param head
     * @return
     */
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        Node slow = head.next;
        Node fast = head.next.next;
        while (slow != fast) {
            if (slow.next == null || slow.next.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;

        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;

        }
        return slow;


    }

    /**
     * 两个无环链表返回交点
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;//两链表相差的距离
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;

        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;

        }
        if (cur1 != cur2) {
            return null;
        }
        cur1 = n > 0 ? head1 : head2;//赋值长的
        cur2 = cur1 == head1 ? head2 : head1;//赋值短的
        n = Math.abs(n);
        while (n != 0) {//将长的来到剩下部分和短的长度一样的位置
            n--;
            cur1 = cur1.next;

        }
        //直到相遇为止
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;


    }


    /**
     * 两个有环链表的交点
     * @param head1
     * @param loop1 入环点1
     * @param head2
     * @param loop2 入环点2
     * @return
     */
    public static Node bothLoop(Node head1,Node loop1,Node head2,Node loop2){
        Node cur1=null;
        Node cur2=null;
        if(loop1==loop2){
            //当交点在入环点前或者就是入环点时
            cur1 = head1;
            cur2 = head2;
            int n = 0;//两链表相差的距离
            while (cur1!= loop1) {
                n++;
                cur1 = cur1.next;

            }
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;

            }
            cur1 = n > 0 ? head1 : head2;//赋值长的
            cur2 = cur1 == head1 ? head2 : head1;//赋值短的
            n = Math.abs(n);
            while (n != 0) {//将长的来到剩下部分和短的长度一样的位置
                n--;
                cur1 = cur1.next;

            }
            //直到相遇为止
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }else {
            //当交点在环上且不是入环点时
            cur1=loop1.next;
            while (cur1!=loop1){//判断一个环遍历完没有相遇说明两环无交点
                if(cur1==loop2){
                    return loop1;
                }
                cur1= cur1.next;
            }
            return null;
        }
    }


    /**
     * 传入两个有环或无环的链表查找交点
     * @param head1
     * @param head2
     * @return
     */
    public static Node getIntersectNode(Node head1,Node head2){
        if(head1==head2){
            return null;
        }
        Node loop1=getLoopNode(head1);
        Node loop2=getLoopNode(head2);
        if(loop1==null&&loop2==null){
            return noLoop(head1,head2);
        }
        if(loop1!=null&&loop2!=null){
            return bothLoop(head1,loop1,head2,loop2);
        }
        return null;
    }


}
